package basic.study.wantOffer.chapter6;

import java.util.LinkedList;

/**
 * @ClassName Problem63
 * @Description 圆圈中剩下的数字
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/14 21:14
 * @Version 1.0
 */
public class Problem62 {
    /**
     * 方法一：模拟约瑟夫环，使用循环链表或者LinkedList
     */
    public int LastRemaining_Solution2(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int removeIndex = 0;
        while (list.size() > 1) {
            removeIndex =  ( + m - 1) % list.size();
            list.remove(removeIndex);
        }
        return list.getFirst();
    }
    /**
     * 方法二：采用推导出来的方法
     */
    public int LastRemaining_Solution(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;//出错
        }
        int last = 0;
        for (int i = 2; i <= n; i++) {
            last = (last + m) % i;
        }
        return last;
    }
}
